package com.aaron.leetcode.lc773;

import java.util.*;

/*
    在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

    一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

    最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

    给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
 */
class Solution_773 {

    //计算最小步数->BFS
    //BFS暴力搜索算法，只要涉及暴力穷举的问题，BFS 就可以用，而且可以最快地找到答案。
    /*
        输入：board = [[4,1,2],[5,0,3]] 输出：5 解释： 最少完成谜板的最少移动次数是 5 ，
        一种移动路径:
        尚未移动: [[4,1,2],[5,0,3]]
        移动 1 次: [[4,1,2],[0,5,3]]
        移动 2 次: [[0,1,2],[4,5,3]]
        移动 3 次: [[1,0,2],[4,5,3]]
        移动 4 次: [[1,2,0],[4,5,3]]
        移动 5 次: [[1,2,3],[4,5,0]]
     */
    int[][] board = new int[2][3];

    {
        board[0] = new int[]{4, 1, 2};
        board[1] = new int[]{5, 0, 3};
    }

    int[][] board2 = new int[2][3];

    {
        //[[3,2,4],[1,5,0]]
        //123450->123405->103425->130425->135420->135402->135042->035142->305142->345102->345120->340125->304125->324105--14步
        board2[0] = new int[]{3, 2, 4};
        board2[1] = new int[]{1, 5, 0};
    }

    //记录最先找到的一条最短路径
    public int slidingPuzzleRecordPath(int[][] board) {
        int m = 2, n = 3;
        String start = "";
        String target = "123450";
        //转成一维字符串
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                start = start + board[i][j];
            }
        }

        // 记录一维字符串的相邻索引
        List<List<Integer>> neighbor =
                Arrays.asList(
                        Arrays.asList(1, 3 ),
                        Arrays.asList(0, 4, 2),
                        Arrays.asList(1, 5),
                        Arrays.asList(0, 4 ),
                        Arrays.asList(3, 1, 5),
                        Arrays.asList(4, 2)
                );

        Queue<Node> queue = new LinkedList<>();
        Node startNode = new Node();
        startNode.setValue(start);
        queue.offer(startNode);

        //访问路径；防止重复走
        //走过的路径直接添加进来，后来的路径如果已经存在，那说明后来的步数>=之前添加进来那次的步数，所以直接不选取
        Set<String> visited = new LinkedHashSet<>();
        visited.add(start);

        int step = 0;

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                Node node = queue.poll();

                //到达目标，直接返回，此时为最小路径，打印最小路径
                if (target.equals(node.getValue())) {
                    Queue<String> path = new LinkedList<>();
                    while (null != node.parent) {
//                        System.out.print(node.getValue()+"<-");
                        path.offer(node.getValue());
                        node = node.parent;
                    }
                    while (!path.isEmpty()) {
                        System.out.print(path.poll() + "->");
                    }

                    return step;
                }

                List<Integer> ajacent = neighbor.get(node.getValue().indexOf('0'));
                for (int j = 0; j < ajacent.size(); j++) {
                    char[] chars = node.getValue().toCharArray();
                    //得到0的位置，换成ajacent.get(j)位置的字符
                    chars[node.getValue().indexOf('0')] = chars[ajacent.get(j)];
                    //把邻接元素的位置换成0 ，ajacent.get(i)
                    chars[ajacent.get(j)] = '0';
                    String oneStep = String.valueOf(chars);//char[].toString() 是hashCode
                    if (!visited.contains(oneStep)) {
                        Node childNode = new Node(oneStep);
                        childNode.parent = node;
                        node.addChild(childNode);
                        queue.add(childNode);
                        visited.add(oneStep);
                    }
                }
            }
            step++;
        }

        //找不到路径，返回-1
        return -1;

    }

    int BFS(Node start, Node target) {

        Queue<Node> q = new LinkedList<>();
        Set<Node> visited = new LinkedHashSet<>();

        q.offer(start);
        visited.add(start);
        int step = 0;

        while (!q.isEmpty()) {
            int sz = q.size();
            //在这里for，为了算step，分清是哪一层
            //大华那个，只要保证所有的组织都查询一遍，所以添到queue中while就行
            for (int i = 0; i < sz; i++) {
                Node cur = q.poll();
//                if (cur is target){
//                    return step;
//                }
//                for(Node x: cur.adj()){
//                    if (x not in visited){
//                        q.offer(x);
//                        visited.add(x);
//                    }
//                }
            }
            step++;
        }


        return -1;
    }

    //返回最短路径数
    public int slidingPuzzle(int[][] board) {
        int m = 2, n = 3;
        String start = "";
        String target = "123450";
        //转成一维字符串
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                start = start + board[i][j];
            }
        }

        // 记录一维字符串的相邻索引
        List<List<Integer>> neighbor =
                Arrays.asList(
                        Arrays.asList(1, 3 ),
                        Arrays.asList(0, 4, 2),
                        Arrays.asList(1, 5),
                        Arrays.asList(0, 4 ),
                        Arrays.asList(3, 1, 5),
                        Arrays.asList(4, 2)
                );

        Queue<String> queue = new LinkedList<>();
        queue.offer(start);

        //访问路径；防止重复走
        //走过的路径直接添加进来，后来的路径如果已经存在，那说明后来的步数>=之前添加进来那次的步数，所以直接不选取
        Set<String> visited = new LinkedHashSet<>();
        visited.add(start);

        int step = 0;

        while (!queue.isEmpty()) {

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String node = queue.poll();

                //到达目标，直接返回，此时为最小路径，打印最小路径
                if (target.equals(node)) {
                    return step;
                }

                List<Integer> ajacent = neighbor.get(node.indexOf('0'));
                for (int j = 0; j < ajacent.size(); j++) {
                    char[] chars = node.toCharArray();
                    //得到0的位置，换成ajacent.get(j)位置的字符
                    chars[node.indexOf('0')] = chars[ajacent.get(j)];
                    //把邻接元素的位置换成0 ，ajacent.get(i)
                    chars[ajacent.get(j)] = '0';
                    String oneStep = String.valueOf(chars);//char[].toString() 是hashCode
                    if (!visited.contains(oneStep)) {
                        queue.offer(oneStep);
                        visited.add(oneStep);
                    }
                }
            }
            step++;
        }

        //找不到路径，返回-1
        return -1;
    }

    public static void main(String[] args) {

        Solution_773 solution_773 = new Solution_773();
        int ans = solution_773.slidingPuzzle(solution_773.board2);
        System.out.println("ans:"+ans);
        int ansRecordPath = solution_773.slidingPuzzleRecordPath(solution_773.board2);
        System.out.println("ansRecordPath:"+ansRecordPath);

    }
}

class Node {

    String value;

    List<Node> children = new ArrayList<>();

    Node parent;

    Node(){

    }

    Node(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    public boolean addChild(Node childNode){
        return this.children.add(childNode);
    }
}